import java.io.*;
import java.util.*;

public class Main {
    public static void main1(String[] args) {
        Scanner in=new Scanner(System.in);
        String str1=in.nextLine();
        String str2=in.nextLine();
        int n=str1.length(),m=str2.length();
        if(n<m) System.out.println("No");
        else {
            int[] hash=new int[26];
            for (int i = 0; i < n; i++) {
                hash[str1.charAt(i)-'A']++;
            }
            int k=0;
            for (k = 0; k < m; k++) {
                if(hash[str2.charAt(k)-'A']!=0) hash[str2.charAt(k)-'A']--;
                else {
                    System.out.println("No");
                    break;
                }
            }
            if(k==m) System.out.println("Yes");
        }
    }

    public static void main2(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        long[] num = new long[3 * n];
        for (int i = 0; i < num.length; i++) {
            num[i] = in.nextLong();
        }
        Arrays.sort(num);
        long ret = 0, k = 0;
        int l=num.length;
        for (k = 0; k < n; k++) {
            l -= 2;
            ret += num[l];
        }
        System.out.println(ret);
    }

    public static void main3(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] num=new int[n];
        for (int i = 0; i < n; i++) {
            num[i]= in.nextInt();
        }
        int[] f=new int[n];
        int[] g=new int[n];
        f[0]=num[0];
        for (int i = 1; i < n; i++) {
            f[i]=g[i-1]+num[i];
            g[i]=Math.max(g[i-1],f[i-1]);
        }
        System.out.println(Math.max(g[n-1],f[n-1]));
    }

    public static void main4(String[] args) {
        Scanner in = new Scanner(System.in);
        int a= in.nextInt(),b= in.nextInt();
        int x=Math.min(a,b);
        b=Math.max(a,b);
        a=x;
        for (int i = b; i <= a*b; i += b) {
           if(i%a==0) {
               System.out.println(i);
               break;
           }
        }
    }

    public static void main5(String[] args) {
        Scanner in=new Scanner(System.in);
        int n= in.nextInt(),m= in.nextInt();
        String[] strings=new String[n];
        for (int i = 0; i < n; i++) {
            strings[i]= in.next();
        }
        char[][] arr=new char[n][m];
        for (int i = 0; i < n; i++) {
            arr[i]=strings[i].toCharArray();
        }
        int[][] dp=new int[n+1][m+1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                int num=0;
                if(arr[i-1][j-1]=='l') num=4;
                else if(arr[i-1][j-1]=='o') num=3;
                else if (arr[i-1][j-1]=='v') num=2;
                else if (arr[i-1][j-1]=='e') num=1;
                dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1])+num;
            }
        }
        System.out.println(dp[n][m]);
    }

    public static void main6(String[] args) {
        Scanner in=new Scanner(System.in);
        double n=in.nextDouble();
        double ret=Math.sqrt(n);
        double num=Math.floor(ret);
        double num2=Math.ceil(ret);
        long sum=0;
        if(Math.abs((num*num)-ret)>Math.abs((num2*num2)-ret)){
            sum=(long)(num2*num2);
        }
        else {
            sum=(long)(num*num);
        }
        System.out.println(sum);
    }
    static int n,m;
    static Map<Integer,Integer> hash=new HashMap<>();
    public static boolean check(int s){
        int g=0;
        for (int a:hash.values()){
           g+=a/s+(a%s==0?0:1);
        }
        return g<=m;
    }
    public static void main7(String[] args) {
        Scanner in=new Scanner(System.in);
        n= in.nextInt();
        m= in.nextInt();
        int max=0;
        for (int i = 0; i < n; i++) {
            int x= in.nextInt();
            hash.put(x,hash.getOrDefault(x,0)+1);
            max=Math.max(max,hash.get(x));
        }
        if(hash.size()>m) System.out.println(-1);
        else {
            int l=1,r=max;
            while (l<r){
                int mid=(l+r)/2;
                if(check(mid)){
                    r=mid;
                }
                else l=mid+1;
            }
            System.out.println(l);
        }
    }
    public String formatString (String str, char[] arg) {
        StringBuilder sb=new StringBuilder();
        int i=0,k=0;
        for (i = 0; i < str.length(); i++) {
            if(str.charAt(i)!='%') sb.append(str.charAt(i));
            else {
                i++;
                sb.append(arg[k++]);
            }
        }
        while (k<arg.length) sb.append(arg[k++]);
        return sb.toString();
    }
    public static boolean ismirnum(int x){
        if(x<2) return true;
        for (int i = 2; i < Math.sqrt(x); i++) {
            if(x%i==0) return false;
        }
        return true;
    }
    public static int vis(int num){
        int[] sum=new int[10];
        int n=0;
        while (num>0){
            sum[n++]=num%10;
            num/=10;
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if(sum[i]!=0&&i!=j){
                    if(ismirnum(sum[i]*10+sum[j])){
                        return 1;
                    }
                }
            }
        }
        return 0;
    }
    public static void main8(String[] args) {
        Scanner in=new Scanner(System.in);
        int l= in.nextInt(),r=in.nextInt();
        int ret=0;
        for(l=Math.max(10,l);l<=r;l++){
            ret+=vis(l);
        }
        System.out.println(ret);
    }

    public static void main9(String[] args) {
        Scanner in=new Scanner(System.in);
        String str=in.next();
        int n= in.nextInt();
        int max=0;
        int[] count=new int[str.length()-n];
        for (int i = 0; i < str.length()-n; i++) {
            String subStr=str.substring(i,i+n);
            for (int j = 0; j < n; j++) {
                if(subStr.charAt(j)=='C'||subStr.charAt(j)=='G'){
                    count[i]++;
                }
            }
            if(count[i]>count[max]){
                max=i;
            }
        }
        String ret=str.substring(max,max+n);
        System.out.println(ret);
    }

    public static void main10(String[] args) {
        Scanner in=new Scanner(System.in);
        String str=in.next();
        int ret=0;
        for (int i = 0; i < str.length(); i++) {
           if((str.charAt(i)-'0')%2==0) ret=ret*10+0;
           else ret=ret*10+1;
        }
        System.out.println(ret);
    }
    static class Read{
        StringTokenizer st=new StringTokenizer("");
        BufferedReader bf=new BufferedReader(new InputStreamReader(System.in));
        String next() throws IOException {
            while (!st.hasMoreTokens()){
                st = new StringTokenizer(bf.readLine());
            }
            return st.nextToken();
        }
        String nextLine() throws IOException {
            return bf.readLine();
        }
        int nextInt() throws IOException {
            return Integer.parseInt(next());
        }
        long nextLong() throws IOException {
            return Long.parseLong(next());
        }
        double nextDouble() throws IOException {
            return Double.parseDouble(next());
        }
        float nextFloat() throws IOException {
            return Float.parseFloat(next());
        }
    }
    public static Read in=new Read();
    public static PrintWriter out=new PrintWriter(new OutputStreamWriter(System.out));
    public static void main11(String[] args) throws IOException {
         int n=in.nextInt(),m= in.nextInt();
         int[][] nums=new int[n][m];
        int[] sumRow=new int[n];
        int[] sumCol=new int[m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                nums[i][j]= in.nextInt();
                sumRow[i]+=nums[i][j];
                sumCol[j]+=nums[i][j];
            }
        }
        int[][] ret=new int[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                ret[i][j]=sumRow[i]+sumCol[j]-nums[i][j];
            }
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                out.print(ret[i][j]);
                if(j!=m-1) out.print(" ");
            }
            out.println();
        }
        out.close();
    }

    public static void main12(String[] args) throws IOException {
        int n= in.nextInt(),k= in.nextInt();
        long[] f=new long[n+1],g=new long[n+1];
        for (int i = 1; i <= n; i++) {
            f[i]=in.nextLong();
            g[i]= in.nextLong();
        }
        int fSum=0,gSum=0,fMax=0,gMin=Integer.MAX_VALUE,begin=0;
        int left=1,right=1;
        while (right<=n){
            fSum+=f[right];
            gSum+=g[right];
            if(right-left+1>k){
                fSum-=f[left];
                gSum-=g[left];
                left++;
            }
            if(right-left+1==k){
                if(fSum>fMax){
                    fMax=fSum;
                    begin=left;
                    gMin=gSum;
                }
                if(fSum==fMax&&gSum<gMin) {
                    gMin=gSum;
                    begin=left;
                }
            }
            right++;
        }
        out.println(begin);
        out.close();
    }
    public String compressString (String param) {
        if(param.length()==0||param.length()==1) return param;
        StringBuilder sb=new StringBuilder();
        int left=0,right=0;
        sb.append(param.charAt(left));
        while (right<param.length()){
            if(param.charAt(right)!=param.charAt(left)){
                if(right-left>1) sb.append((char) (right-left));
                left=right;
                sb.append(param.charAt(left));
            }
            right++;
        }
        if(right-left>1) sb.append((char) (right-left));
        return sb.toString();
    }
   static class Orange{
        int a;
        int b;
        public Orange(){}

    }
    public static void main13(String[] args) throws IOException {
        int n=in.nextInt(),k= in.nextInt();
        Orange[] o=new Orange[n];
        for (int i = 0; i < n; i++) {
            o[i]=new Orange();
            o[i].a=in.nextInt();
        }
        for (int i = 0; i < n; i++) {
            o[i].b= in.nextInt();
        }
        Arrays.sort(o,(x,y)->{
            if(x.b == y.b) return x.a - y.a;
            else return y.b - x.b;
        });
        long x=0,y=0;
        for (int i = 0; i < k; i++) {
            x+=o[i].a;
            y+=o[i].b;
        }
        out.print(x+" "+y);
        out.close();
    }
    int[] dp=new int[1001];
    public int knapsack (int V, int n, int[][] vw) {
        for (int i = 0; i < n; i++) {
            for (int j = V; j >= vw[i][0]; j--) {
                dp[j]=Math.max(dp[j],dp[j-vw[i][0]]+vw[i][1]);
            }
        }
        return dp[V];
    }
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int[] nums3=new int[nums1.length+nums2.length];
        int k=0,i=0,j=0;
        while(i<nums1.length&&j<nums2.length){
            if(nums1[i]>nums2[j]){
                nums3[k++]=nums2[j++];
            }
            else{
                nums3[k++]=nums1[i++];
            }
        }
        if(i>=nums1.length){
            while(j<nums2.length){
                nums3[k++]=nums2[j++];
            }
        }
        if(j>=nums2.length){
            while(i<nums1.length){
                nums3[k++]=nums1[i++];
            }
        }
        if(nums3.length%2!=0){
            return (double)nums3[nums3.length/2];
        }
        double mid=(nums3[nums3.length/2]+nums3[nums3.length/2-1])/2.0;
        return mid;
    }
}